package leetCode.solution;

import java.util.LinkedList;

/**
 * 给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k
 * 个数字。滑动窗口每次只向右移动一位。
 * 
 * 返回 滑动窗口中的最大值 。
 * 
 * @author jerry
 * @ClassName: Solution239
 * @Description:TODO(描述这个类的作用)
 * @date 2022年12月19日 下午5:34:13
 */
public class Solution239 {

	public int[] maxSlidingWindow(int[] nums, int k) {

		int[] result = new int[nums.length - k + 1];
		LinkedList<Integer> queue = new LinkedList<Integer>();

		for (int i = 0; i < k; i++) {
			while (!queue.isEmpty() && nums[queue.peekLast()] < nums[i]) {
				queue.pollLast();
			}
			queue.offerLast(i);
		}
		result[0] = nums[queue.peekFirst()];
		for (int i = k; i < nums.length; i++) {
			while (!queue.isEmpty() && nums[queue.peekLast()] < nums[i]) {
				queue.pollLast();
			}
			queue.offerLast(i);
			while (queue.peekFirst() <= i - k) {
				queue.pollFirst();
			}
			result[i - k + 1] = nums[queue.peekFirst()];
		}

		return result;
	}
}